package com.zhongge.binarytreeOJ.question;
import com.zhongge.binarytreeOJ.MyBinaryTree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName IsSubtree
 * @Description TODO
 * @Author zhongge
 * @Date 2025/9/3 17:03
 * @Version 1.0
 */
public class IsSubtree {
    List<TreeNode> list = new ArrayList<>();

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //第一步：安全校验
        if (p == null && q == null) {
            return true;
        }
        //到这里：p!=null || q!=null
        if (p == null) {//p == null&&q!=null
            return false;
        }

        if (q == null) {//q == null&&p != null
            return false;
        }
        //到这里 p!=null && q!=null
        //那么此时就看结构：由左右子树的情况
        if (p.left != null && q.left == null ||
                p.left == null && q.left != null) {
            return false;
        } else if(p.right != null && q.right == null ||
                p.right == null && q.right != null) {
            return false;
        } else {
            //到这里说明 p.left != null && q.left != null
            // p.right != null && q.right != null
            //结构相同那么就比较左右子树的值
            if (p.val != q.val) {
                return false;
            } else {//值相同
                //那么此时就比较左右子树是否相同
                return  (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
            }
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //首先安全校验
        if (root == null && subRoot == null) {
            return true;
        }
        //到这里==》root !=null || subRoot != null
        if (root == null){//root == null && subRoot != null
            return false;
        }
        if (subRoot == null) {//root != null && subRoot == null
            return true;
        }
        //到这里 root != null && subRoot != null
        //那么此时在root中找到subRoot的根

        boolean find = findValue(root, subRoot.val);
        if (!find) {
            return false;
        }
        //到这里就是找到了值
        TreeNode sub = list.getFirst();
        //那么就是判断 两颗树是否相同
        boolean isSame = isSameTree(sub, subRoot);
        if (isSame) {
            return true;
        }
        return false;
    }

    private boolean findValue(TreeNode root, int val) {
        //安全检验==》递归出口
        if (root == null) {
            return false;
        }
        //递归剪枝：找到就提前结束递归
        if (root.val == val) {
            list.add(root);
            return true;//找到就直接返回了
        }
        //递归的递
        boolean left = findValue(root.left, val);
        if (left) {
            return true;
        }
        boolean right =findValue(root.right, val);
        if (right) {
            return true;
        }
        //递归的归
        //到这里说明左右都没有找到
        return false;
    }

}
